package com.LeeCode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的后序遍历
 */

public class Code145 {
    public static void main(String[] args) {

    }

    List<Integer> ans = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        posterorder(root);
        return ans;
    }

    private void posterorder(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        ans.add(root.val);
    }

    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root, prev = null;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.peek();

            // 没有右子树或者右子树已经被访问过了
            if (node.right == null || node.right == prev) {
                ans.add(node.val);
                prev = node;
                node = null;  // 防止重复访问左子树
                stack.pop(); // 出栈
            } else {   // 还有未访问过的的右子树
                node = node.right;
            }
        }

        return ans;
    }
}
